package leetcode.code2271;

import java.util.Arrays;

import leetcode.IDebug;

public class Solution implements IDebug {

	public int maximumWhiteTiles(int[][] tiles, int carpetLen) {
		Arrays.sort(tiles, (a, b) -> a[0] - b[0]);
		int indexL = 0;
		int range = tiles[indexL][0] + carpetLen;
		int ans = Integer.MIN_VALUE;
		int size = 0;// 毯子下的白块数量
		int p = 0;
		while (p < tiles.length) {
			int[] cur = tiles[p];
			int li = cur[0], ri = cur[1];
			int curSize = ri - li + 1;
			// 区间比毯子长，毯子多长就能盖多少
			if (curSize >= carpetLen) {
				return carpetLen;
			}
			// 毯子范围内的区间，除最后一个，都比毯子短
			if (ri < range) {
				// 当前区间完全被毯子覆盖
				size += curSize;
				p++;
			} else {
				if (li >= range) {
					// 当前区间，毯子一点盖不到
					ans = Math.max(ans, size);
				} else {
					// 当前区间毯子能盖着一点
					ans = Math.max(ans, size + range - li);
				}
				size -= tiles[indexL][1] - tiles[indexL][0] + 1;
				indexL = indexL + 1;
				range = tiles[indexL][0] + carpetLen;
			}
		}
		ans = Math.max(ans, size);
		return ans;
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
